Majority Elements Series

发表于

Majority Element

Question

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Analysis

Boyer-Moore Majority

直接Array排序后找最多会超时

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int majorityElement(int[] num) {
        int major=num[0], count = 1;
        for(int i=1; i<num.length;i++){
            if(count==0){
                count++;
                major=num[i];
            }else if(major==num[i]){
                count++;
            }else count--;
            
        }
        return major;
    }
}

Majority Element II

Question

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Analysis

最多只可能有两个符合条件的元素，利用两个cnt和num记录

第一次遍历找到可能符合条件的num，再一次遍历确定是否超过n/3

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res=new ArrayList<>();
        if(nums.length==0)  return res;
        int cnt1=0;
        int cnt2=0;
        int num1=0;
        int num2=1;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==num1)
                cnt1++;
            else if(nums[i]==num2)
                cnt2++;
            else if(cnt1==0){
                cnt1=1;
                num1=nums[i];
            }
            else if(cnt2==0){
                cnt2=1;
                num2=nums[i];
            }
            else{
                cnt1--;
                cnt2--;
            }
        }
        int count1=0;
        int count2=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==num1)
                count1++;
            else if(nums[i]==num2)
                count2++;
        }
        if(count1>nums.length/3)    res.add(num1);
        if(count2>nums.length/3)    res.add(num2);
        return res;
    }
}